Lesson 13
Timothy Luna
9/15/2019
2C-L3 Aliasing
Intro
Today’s lesson is the denoumont of how frequency explains the notion of aliasing. Return to the idea of using Fourier to obtain basis sets of an image where we decompose the image terms of sinusoidal bases. (Return to the image of Abraham Lincoln decomposed into vertical and horizontal frequencies.)
We’ve talked about the relationship between convolution and multiplication as you go between the spatial and frequency domain.
Today it’s very important that multiplication in the spatial domain is convolution in the frequency domain.
Fourier Transform Sampling Pairs
There is an important pair for today’s lesson: The Fourier transform of a Comb function (a pulse train, or a set of impulses) is another Comb function but as the pulses in space get farther apart the pulses in frequency space get closer together. As the distance between impulses in space grows to infinity we approach a single impulse function and the convolution is a solid bar!
Sampling and Reconstruction
What is sampling? What is reconstruction? Here is a nice, smooth, scene with a light source and then some device that captures intensity at a bunch of discrete locations.
We would like to take the discrete capture and reconstruct the nice, smooth, original signal.
Sampling arises from the question of how to store a smooth signal in a computer. One obvious way is to take samples of the signal at a number of locations and write down the values. Given that set of samples later you want to reconstruct the signal in order to play it through the speaker, or on the television, or to use it mathematically.
You have to guess at what’s going on in the unsampled space.
This one-dimensional audio example has time on the x axis. The frequency starts low and gets higher and higher until it stops.
This is a chirp; it’s often used with radar style applications to ensure that some signal returns.
Sampling in Digital Audio
Continuing on with the audio example; the image on the right depicts a microphone receiving a continuous voltage signal. In order to encode that it must pass through an analog to digital convertor to be turned into a set of samples in a file.
When this is played it pulls out the samples and goes through a digital to analog convertor to be turned into a continuous signal in order to be played as music!
Audio
This example of sampling uses a sin wave. Collecting a bunch of samples, how can those samples be reconstructed? Given enough samples you can just linearly interpolate between the samples!
Undersampling
But what if we don’t have enough samples? If we undersample then, unsurprisingly, information is lost.
Interestingly, though, the sampled points can fit other frequency curves. Both lower and higher frequencies could produce the same sampled signal. This is an example of aliasing.
Aliasing
Aliasing is when you are given a signal and cannot distinguish between a low and a high frequency.
This is also something that happens in time. The instructor gives an example of a propellor starting to spin up and, as it spings up, there comes a time where the propeller appears to move backwards and then returns to moving forwards.
The video or film can only take so many samples and when the rotational frequency of the propellers just happens to be a tiny bit off from the sampling frequency you see the propeller spinning backwards.
Undersampled
Low Frequency Which Matches Samples
High Frequency Which Matches Samples
In the image below you see a signal (left) translated into an image (right) and the image shows the effects of aliasing. That is because there isn’t enough delineation amongst the pixels to capture a frequency that high!
Aliasing Example
Antialiasing
So, how do we fix sampling issues? One way would be to increase the discretization. Better cameras, more fidelity in the image, less problems from sampling! This can’t go on forever, though, so what else could we do?
We can remove some of the high frequency information, which isn’t great but is better than aliasing.
Going back to the audio example we’re going to introduce a ‘lowpass filter’ on the right side of the microphone to ensure that the signal going into the analog to digital convertor doesn’t have any signals beyond a threshold. Now when the signal is reconstructed any frequency higher than that threshold is discarded.
Impulse Train and Bed of Nails
Let’s take that idea of removing high frequency signal into the frequency domain!
- Define a comb function (impulse train) in one-dimension as \(comb_M[x]=\sum_{k=-\infty}^{\infty} \delta[x-kM]\) where \(M\) is some integer.
\(\delta(x)\), or the ‘delta’ function, is a function that is equal to one when the input is zero and zero otherwise. This means that at \(x-kM\) the delta function returns one. Hence, the comb.
M = 2
Remember that the Fourier transform of a comb function is simply another comb function, but the scaling property of the Fourier transform means that as the space between impulses in the spatial domain rises the space between impulses in the frequency domain falls.
Fourier Transform of Comb Function Scales
You can also do impulses in two dimensions.
\[comb_{M,N}(x,y)=\sum_{k=-\infty}^{\infty}\sum_{l=-\infty}^{\infty}\delta(x-kM,y-lN)\]
This is called a ‘bed of nails’ because it’s impulses in two dimensions and resembles a bed of nails!
The Fourier transform of a bed of nails is another bed of nails and shares the same relationship with the Fourier transform of a one-dimensional comb function.
Sampling Low Frequency Signal
Sampling is multiplying a continuous signal by a discrete comb function. Multiplication in the spatial domain is convolution in the frequency domain, so we convolve the Fourier transform of f with the Fourier transform of the comb function and we get the Fourier transform of f * comb.
This function has almost no high frequency components!
The bottom right is the Fourier transform of the comb times the function and can be used to reconstruct the original signal.
If this function is limited to the frequencies within some range then we can nearly perfectly reconstruct the original function.
If the frequency domain representation does not have any overlap and the width between the peaks then if the maximum frequency of the original function (\(W\)) is less than one over twice the distance between the original comb impulses. \(W<\frac{1}{2M}\).
If you want to recover something up to 20kHz you need to sample at a frequency of at least 40kHz.
The extent of human hearing is 22 kHz.
Sampling Low Frequency Signal
Reconstruction Requirements
Sampling High Frequency Signal
As long as your frequencies are low enough you are ok. What if they are not?
If the original function has a higher frequency note that its W goes out further in the frequency domain representation. The convolved result has overlapping signals which will sum at the overlap. This high frequency which was the edge is pretending to be low frequency now.
Aliasing is unrecoverable. You must remove the high frequencies prior to sampling.
How do you remove high frequencies? You can convolve with a Gaussian!
Overlapping Frequencies
Reducing the high frequencies can remove the overlap and prevent aliasing. Thus in \(f(x)*h(x)\) h is referred to as an ‘anti-aliasing’ filter and effectively trims high frequencies from the image.
After that, multipling by the comb shows no overlap!
To recover the signal you can throw away any high frequencies beyond those excluded in the original filter.
Anti-Aliasing
Aliasing in Images
This is an example of aliasing in an image, note the top left where high frequencies exist. This means that we have to be careful, though, because sometimes this will affect the operations we want to do!
What happens when you want to reduce the size of an image? Can we just throw away every other row?
Well, you can, but this causes aliasing and the resultant image will not perfectly represent the original image.
So, what’s the right thing to do. We can do anti-aliasing!
Let’s use a Gaussian (lowpass) pre-filter and then subsample. This results in something that much more closely resembles the original image.
Campbell-Robson Contrast Sensitivity
Psycho-physisicts studied the contrast sensitivity of the human eye.
This image is a good representation of what human beings can see!
Some frequencies matter more to human beings. The ones that don’t matter can be used to do image compression!
Visible Frequency Spectra
Image Compression
JPEG uses a discrete cosine transform (or similar) where they take an eight by eight chunk of the image, then takes as a basis set a set of sinusoids and you can specify how much of each frequency set you need to represent the image. Those that aren’t highly prevalent can just be encoded with more bits than those that are necessary.
A quantization table tells you how many bits you use to represent the image.
